Search for: All records

Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a generalization of this classical problem in which the position of each vertex in the graph is a continuous decision variable, constrained to lie in a corresponding convex set. The length of an edge is then defined as a convex function of the positions of the vertices it connects. Problems of this form arise naturally in motion planning of autonomous vehicles, robot navigation, and even optimal control of hybrid dynamical systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NP-hard. Our main contribution is a strong mixed-integer convex formulation based on perspective functions. This formulation has a very tight convex relaxation and makes it possible to efficiently find globally-optimal paths in large graphs and in high-dimensional spaces. 

Shear flow-induced migration is an important physiological phenomenon experienced by multiple cell types, including leukocytes and cancer cells. However, molecular mechanisms by which cells sense and directionally migrate in response to mechanical perturbation are not well understood. Dictyostelium discoideum social amoeba, a well-established model for studying amoeboid-type migration, also exhibits directional motility when exposed to shear flow, and this behavior is preceded by rapid and transient activation of the same signal transduction network that is activated by chemoattractants. The initial response, which can also be observed following brief 2 s stimulation with shear flow, requires an intact actin cytoskeleton; however, what aspect of the cytoskeletal network is responsible for sensing and/or transmitting the signal is unclear. We investigated the role of actin crosslinkers filamin and α-actinin by analyzing initial shear flow-stimulated responses in cells with or without these proteins. Both filamin and α-actinin showed rapid and transient relocalization from the cytosol to the cortex following shear flow stimulation. Using spatiotemporal analysis of Ras GTPase activation as a readout of signal transduction network activity, we demonstrated that lack of α-actinin did not reduce, and, in fact, slightly improved the response to acute mechanical stimulation compared to cells expressing α-actinin. In contrast, shear flow-induced Ras activation was significantly more robust in filamin-null cells rescued with filamin compared to cells expressing empty vector. Reduced responsiveness appeared to be specific to mechanical stimuli and was not due to a change in the basal activity since response to global stimulation with a chemoattractant and random migration was comparable between cells with or without filamin. Finally, while filamin-null cells rescued with filamin efficiently migrated upstream when presented with continuous flow, cells lacking filamin were defective in directional migration. Overall, our study suggests that filamin, but not α-actinin, is involved in sensing and/or transmitting mechanical stimuli that drive directed migration; however, other components of the actin cytoskeleton likely also contribute to the initial response since filamin-null cells were still able to activate the signal transduction network. These findings could have implications for our fundamental understanding of shear flow-induced migration of leukocytes, cancer cells and other amoeboid-type cells.